package com.lwx.leetcode.dp;

/**
 * 最长回文子序列 - 递归写法
 */
public class Offer516 {
    public static void main(String[] args) {
        Offer516 o = new Offer516();
        String s = "bbbab";
        int length = o.longestPalindromeSubseq(s);
        System.out.println(length);
    }
    public String str;
    public int longestPalindromeSubseq(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        str = s;
        return palindromeSubseqLength(0,s.length()-1);
    }

    public int palindromeSubseqLength(int start,int end){
        if(start > end){
            return 0;
        }
        if(start == end){
            return 1;
        }
        if(str.charAt(start) == str.charAt(end)){
            return palindromeSubseqLength(start +1, end-1) + 2;
        }else {
            return Math.max(palindromeSubseqLength(start +1, end), palindromeSubseqLength(start, end-1));
        }
    }
}
